The invention relates generally to managing a re-usable resource, and more particularly to managing a pool of integers using a linked list of elements that are stored in computer memory.
Linked lists are widely used to link blocks of related data within computer memory and to identify blocks of memory that are available to store data. FIG. 1 depicts a series of available memory blocks 102 (also referred to as a xe2x80x9cfreexe2x80x9d list) that are linked together by pointers 104 at the end of each block. The head of the free list is a free list pointer 106 that identifies the first free memory block and the end of the free list is identified by a xe2x80x9cnullxe2x80x9d pointer. When memory blocks are needed to store data, the memory blocks are allocated in successive order from the free list by adjusting the free list pointer to exclude allocated memory blocks.
FIG. 2 depicts how the free list head pointer 206 is adjusted to exclude the first memory block 208 that has been allocated to store data. When a memory block is no longer needed to store data, the block can be added to the xe2x80x9cheadxe2x80x9d or xe2x80x9cfrontxe2x80x9d of the free list by adjusting the free list head pointer to identify the newly freed memory block and by adjusting the pointer of the newly freed memory block to identify the next free memory block. Because newly freed memory blocks are added to the head of the list, the free integers are allocated on a last-in first-out (LIFO) basis. This technique for managing memory works well when the memory blocks are needed to store data, however it is not such an efficient technique for managing a list of integers that are available from an integer pool. Managing a list of integers instead of memory blocks is useful in several computing applications. For example, managing a list of integers is useful for allocating asynchronous transfer mode (ATM) virtual circuits (VCs) in an ATM network. Throughout the description, similar reference numbers may be used to identify similar elements.
U.S. Pat. No. 6,233,630 issued to Wilhelm discloses a technique for managing a list of free integers that is memory efficient. The technique involves defining an integer pool by allocating a block of memory for each integer in the pool, with the memory block for each integer consisting entirely of a pointer that identifies the next integer in the linked list of free integers. That is, the integer pool consists entirely of links and therefore the amount of memory required to identify each integer is related to the size of the integer pool. For example 256 integers can be uniquely identified with eight bit pointers. FIG. 3 depicts a linked list of free integers where the integers consist entirely of pointers 304 that indicate the next integer in the list and where the first free integer in the list is indicated by a head element 306. The free integers are allocated in the order of the linked list. For example, when a free integer is needed, the next integer identified by the head element is allocated as indicated in FIG. 4. Allocating an integer (that is, removing the related element from the linked list) involves adjusting the pointer of the head element to identify the next element in the linked list as indicated in FIG. 5. When an allocated integer becomes freed and needs to be added back to the free list, the pointer of the head element is adjusted to identify the linked list element of the newly freed integer and the linked list element of the newly freed integer is adjusted to point to the integer that was previously identified by the head element.
While the technique disclosed by Wilhelm works well to identify a next free integer (i.e., where the next free integer can be any free integer from the integer pool), the technique is not as efficient when a specific integer must be allocated from an integer pool, for example, when trying to reserve a specific ATM VC. A problem involved with allocating a specific integer using a singly linked list is that repairing the linked list of elements is an O(n) operation, where n is the number of integers in the integer pool. That is, allocating a specific integer (for example integer four) involves indexing into the array of linked list elements to the linked list element that represents integer four and then removing the linked list element from the linked list of elements. Removing a specific element from the linked list involves adjusting the pointer value of the element that is directly previous to the specific element to skip over the specific integer. For example, referring to FIG. 6, removing the element that relates to integer four involves adjusting the pointer value of the previous element (i.e., adjusting the pointer for integer three to identify integer five). The problem involved with adjusting the pointer value of the previous element is that the location of the previous element is not readily known. Locating the previous element in a singly linked list is an O(n) operation that involves sequentially searching through the array of elements until the previous element is found. In time critical applications, it is desirable to avoid O(n) operations.
Although the technique described in Wilhelm works well to allocate a unique integer from an integer pool while conserving memory space, in some applications there is a need to allocate specific integers in an efficient manner. As a result, what is needed is an efficient way to allocate free integers from an integer pool that allows the selection of a specific free integer from an integer pool as well as the selection of any free integer from the integer pool.
The invention involves a doubly linked list of elements that represents free integers in an integer pool. Each element of the doubly linked list includes a next pointer for identifying a next element in the linked list and a previous pointer for identifying a previous element in the linked list. A specific free integer can be allocated from the integer pool in an order of one, O(1), operation by indexing into the linked list to the linked list element that represents the integer and then utilizing the next and previous pointers of the linked list element to remove the linked list element from the linked list. The desired linked list element is removed by adjusting the next pointer of the previous linked list element and the previous pointer of the next linked list element. A non-specific free integer can be allocated from the integer pool in an O(1) operation through a head element that identifies a next free integer in the linked list. A non-specific free integer includes any one of the free integers in the linked list of free integers. Utilizing a doubly linked list, a resource allocation scheme that can allocate a specific free integer and a next free integer in O(1) operations is achieved. In contrast to the doubly linked list, allocating a specific integer from a singly linked list would require searching the entire linked list to find the pointer value that is needed to remove the related linked list element. Searching through the entire linked list is an O(n) operation, which requires more processor cycles and is undesirable in time critical operations.
An embodiment of the invention involves a method for managing a reusable resource. According to the method, an array of linked list elements that defines an integer pool is established, wherein each linked list element includes a next pointer for identifying a next linked list element and a previous pointer for identifying a previous linked list element. A doubly linked list that represents free integers in the integer pool is formed from the linked list elements. A head element, having a next pointer for identifying one end of the doubly linked list and a previous pointer for identifying the other end of the doubly linked list, is established. A specific free integer is allocated by locating the linked list element that corresponds to the specific free integer and using the next and previous pointers of the linked list element to remove the linked list element from the doubly linked list, and a next free integer is allocated by accessing the head element and removing, from the doubly linked list, the linked list element that is identified by the next pointer of the head element.
In an embodiment, allocating a specific free integer includes using the next pointer, of the linked list element that corresponds to the specific integer, to identify the next linked list element in the doubly linked list, adjusting the previous pointer of the identified next linked list element to exclude, from the doubly linked list, the linked list element that corresponds to the specific integer, using the previous pointer, of the linked list element that corresponds to the specific integer, to identify the previous linked list element in the doubly linked list, and adjusting the next pointer of the identified previous linked list element to exclude, from the doubly linked list, the linked list element that corresponds to the specific integer. In an embodiment the previous pointer of the identified next linked list element is set to the same value as the previous pointer of the linked list element that corresponds to the specific integer. In an embodiment, the next pointer of the identified previous linked list element is set to the same value as the next pointer of the linked list element that corresponds to the specific integer.
In a further embodiment of the method, an integer can be added to the doubly linked list by identifying an integer that is to be added to the doubly linked list, locating the linked list element that corresponds to the integer that is to be added to the doubly linked list, and adding the linked list element to the doubly linked list using the next or previous pointer of the head element. In one embodiment the linked list element is added to the front of the doubly linked list using the next pointer of the head element, thereby producing a last-in first-out allocation scheme. In another embodiment, the linked list element is added to the end of the doubly linked list using the previous pointer of the head element, thereby producing a first-in first-out allocation scheme.
In a further embodiment of the invention, allocated integers can be identified by forming a doubly linked list that represents the integers that have been allocated from the integer pool and by establishing a head element for the allocated list having a next pointer for identifying one end of the allocated list and a previous pointer for identifying the other end of the allocated list.
The invention is also embodied as a system for managing a reusable resource and as a computer program product for managing a reusable resource. The system and computer program product implement essentially the same technique as the method that is described above.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.